class Solution:
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        from collections import Counter

        ls = len(s)
        lp = len(p)

        if ls < lp:
            return []

        res = []
        pchar = Counter(p)
        count = lp

        # 是一个滑动窗口的模型
        # 这个场景不需要知道每次窗口移动导致字符串有什么具体变化，只需要把握住一个量——满足度（p中有多少字符被满足了）；这样就把异位词这个概念通过一个值量化了
        for i in range(ls):
            if pchar[s[i]] >= 1:
                count -= 1
            pchar[s[i]] -= 1
            if i >= lp:
                if pchar[s[i - lp]] >= 0:
                    count += 1
                pchar[s[i - lp]] += 1
            if count == 0:
                res.append(i - lp + 1)

        return res
        
s = Solution()
print(s.findAnagrams("cbaebabacd", 'abc'))
print(s.findAnagrams("abab", 'ab'))


